// 数组中出现次数超过一半的数字

	// 时间复杂度O(N*logN)
    int majorityElement(vector<int>& nums) {

        std::sort(nums.begin(),nums.end());

        return nums[nums.size()/2];
    }

	// 时间复杂度O(N)
    int majorityElement(vector<int>& nums) {
        int num=nums[0];
        int count=1;
        // 通过计数相消来得到次数超过一半的数字
        for(int i=1;i<static_cast<int>(nums.size());i++)
        {
            if(nums[i]==num)
            {
                count++;
            }
            else
            {   
                if(--count==0)
                {
                    num=nums[i];
                    count=1;
                }
            }
        }
        return num;
    }   

   	// 时间复杂度O(N) 空间复杂度O(N)
    int majorityElement(vector<int>& nums) {
        std::map<int,int> hash;

        for(auto e : nums)
        {
            hash[e]++;
        }

        int half=static_cast<int>(nums.size())/2;

        for(auto e : nums)
        {
            if(hash[e]>half)
            {
                return e;
            }
        }

        return int();
    }

// 按奇偶排序数组 II

	// 时间复杂度O(N) 空间复杂度O(N)
    vector<int> sortArrayByParityII(vector<int>& nums) {

        vector<int> v1; // 奇数
        vector<int> v2; // 偶数

        for(auto e : nums)
        {
            if(e%2==0)
            {
                v2.push_back(e);
            }
            else
            {
                v1.push_back(e);
            }
        }
        int v1i=0;
        int v2i=0;
        for(int i=0;i<static_cast<int>(nums.size());i++)
        {
            if(i%2==0)
            {
                nums[i]=v2[v2i++];
            }
            else
            {   
                nums[i]=v1[v1i++];
            }
        }
        return nums;
    }
	
	// 时间复杂度O(N)
    vector<int> sortArrayByParityII(vector<int>& nums) 
    {
        int prev=0;
        int curr=prev+1;
        // 前后指针
        while(prev<nums.size())
        {
            if(nums[prev]%2==1)
            {
                while(nums[curr]%2==1)
                {
                    curr+=2;
                }
                swap(nums[prev],nums[curr]);
            }
            prev+=2;
        }

        return nums;
    }